package PAT;

import java.util.Scanner;
import java.util.Stack;

public class PAT1057 {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        while (n-- > 0) {
            String s = scanner.nextLine();
            switch (s) {
                case "Pop": {
                    if (stack.isEmpty()) {
                        System.out.println("Invalid");
                    } else {
                        Integer pop = stack.pop();
                        System.out.println(pop);
                    }
                    break;
                }
                case "PeekMedian": {
                    if (stack.isEmpty()) {
                        System.out.println("Invalid");
                    } else {
                        int num = (stack.size() + 1) / 2-1;
                        Integer pop = stack.get(num);
                        System.out.println(pop);
                    }
                    break;
                }
                default:{
                    String[] s1 = s.split(" ");
                    stack.push(Integer.parseInt(s1[1]));
                }
            }
        }
    }
}
